//
// Copyright (C) 2004 Andras Varga
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program; if not, see <http://www.gnu.org/licenses/>.
//


#include <omnetpp.h>
#include <stdlib.h>
#include <string.h>

#include "IP.h"
#include "IPDatagram.h"
#include "IPControlInfo.h"
#include "ICMPMessage_m.h"
#include "IPv4InterfaceData.h"
#include "ARPPacket_m.h"
#include "sha1.h"
Define_Module(IP);

#define MSB_MASK ~((~0U) >> 1)

IP::~IP()
{
	std::map<FlowKey, FlowQueue*>::iterator it;
	for (it = flowQueueCache.begin(); it != flowQueueCache.end(); it++) {
		FlowQueue *flowQueue = it->second;
		if (flowQueue) {
			while (!flowQueue->empty()) {
				delete flowQueue->front();
				flowQueue->pop();
			}
			delete flowQueue;
		}
	}

	std::map<FlowKey, IPDatagram *>::iterator disPacketIt;
	for (disPacketIt = disPacketCache.begin(); disPacketIt != disPacketCache.end(); disPacketIt++) {
		delete disPacketIt->second;
	}
}

void IP::initialize()
{
	QueueBase::initialize();

	ift = InterfaceTableAccess().get();
	rt = RoutingTableAccess().get();

	queueOutGate = gate("queueOut");

	defaultTimeToLive = par("timeToLive");
	defaultMCTimeToLive = par("multicastTimeToLive");
	fragmentTimeoutTime = par("fragmentTimeout");
	mapping.parseProtocolMapping(par("protocolMapping"));

	// threshold values
	threshold_light = par("threshold_light").doubleValue();
	threshold_medium = par("threshold_medium").doubleValue();
	threshold_reset = par("threshold_reset").doubleValue();
	threshold_congestion = par("threshold_congestion").doubleValue();

	curFragmentId = 0;
	lastCheckTime = 0;
	fragbuf.init(icmpAccess.get());

	flowTable = NULL;

	numMulticast = numLocalDeliver = numDropped = numUnroutable = numForwarded = 0;

	WATCH(numMulticast);
	WATCH(numLocalDeliver);
	WATCH(numDropped);
	WATCH(numUnroutable);
	WATCH(numForwarded);
}

void IP::updateDisplayString()
{
	char buf[80] = "";
	if (numForwarded>0) sprintf(buf+strlen(buf), "fwd:%d ", numForwarded);
	if (numLocalDeliver>0) sprintf(buf+strlen(buf), "up:%d ", numLocalDeliver);
	if (numMulticast>0) sprintf(buf+strlen(buf), "mcast:%d ", numMulticast);
	if (numDropped>0) sprintf(buf+strlen(buf), "DROP:%d ", numDropped);
	if (numUnroutable>0) sprintf(buf+strlen(buf), "UNROUTABLE:%d ", numUnroutable);
	getDisplayString().setTagArg("t",0,buf);
}

void IP::endService(cPacket *msg)
{
	if (msg->getArrivalGate()->isName("transportIn"))
	{
		handleMessageFromHL( msg );
	}
	else if (dynamic_cast<ARPPacket *>(msg))
	{
		// dispatch ARP packets to ARP
		handleARP((ARPPacket *)msg);
	}
	else
	{
		IPDatagram *dgram = check_and_cast<IPDatagram *>(msg);
		handlePacketFromNetwork(dgram);
	}

	if (ev.isGUI())
		updateDisplayString();
}

InterfaceEntry *IP::getSourceInterfaceFrom(cPacket *msg)
{
	cGate *g = msg->getArrivalGate();
	return g ? ift->getInterfaceByNetworkLayerGateIndex(g->getIndex()) : NULL;
}

void IP::handlePacketFromNetwork(IPDatagram *datagram)
{
	//
	// "Prerouting"
	//

	// check for header biterror
	if (datagram->hasBitError())
	{
		// probability of bit error in header = size of header / size of total message
		// (ignore bit error if in payload)
		double relativeHeaderLength = datagram->getHeaderLength() / (double)datagram->getByteLength();
		if (dblrand() <= relativeHeaderLength)
		{
			EV << "bit error found, sending ICMP_PARAMETER_PROBLEM\n";
			icmpAccess.get()->sendErrorMessage(datagram, ICMP_PARAMETER_PROBLEM, 0);
			return;
		}
	}

	datagram->getArrivalGateId();
	// remove control info
	delete datagram->removeControlInfo();

	// route packet
	if (!datagram->getDestAddress().isMulticast())
		hashRoutePacket(datagram, false);
	else
		routeMulticastPacket(datagram, NULL, getSourceInterfaceFrom(datagram));
}

void IP::handleARP(ARPPacket *msg)
{
	// FIXME hasBitError() check  missing!

	// delete old control info
	delete msg->removeControlInfo();

	// dispatch ARP packets to ARP and let it know the gate index it arrived on
	InterfaceEntry *fromIE = getSourceInterfaceFrom(msg);
	ASSERT(fromIE);

	IPRoutingDecision *routingDecision = new IPRoutingDecision();
	routingDecision->setInterfaceId(fromIE->getInterfaceId());
	msg->setControlInfo(routingDecision);

	send(msg, queueOutGate);
}

void IP::handleReceivedICMP(ICMPMessage *msg)
{
	switch (msg->getType())
	{
	case ICMP_REDIRECT: // TODO implement redirect handling
	case ICMP_DESTINATION_UNREACHABLE:
	case ICMP_TIME_EXCEEDED:
	case ICMP_PARAMETER_PROBLEM: {
		// ICMP errors are delivered to the appropriate higher layer protocol
		IPDatagram *bogusPacket = check_and_cast<IPDatagram *>(msg->getEncapsulatedMsg());
		int protocol = bogusPacket->getTransportProtocol();
		int gateindex = mapping.getOutputGateForProtocol(protocol);
		send(msg, "transportOut", gateindex);
		break;
	}
	default: {
		// all others are delivered to ICMP: ICMP_ECHO_REQUEST, ICMP_ECHO_REPLY,
		// ICMP_TIMESTAMP_REQUEST, ICMP_TIMESTAMP_REPLY, etc.
		int gateindex = mapping.getOutputGateForProtocol(IP_PROT_ICMP);
		send(msg, "transportOut", gateindex);
	}
	}
}

void IP::handleMessageFromHL(cPacket *msg)
{
	// if no interface exists, do not send datagram
	if (ift->getNumInterfaces() == 0)
	{
		EV << "No interfaces exist, dropping packet\n";
		delete msg;
		return;
	}

	// encapsulate and send
	InterfaceEntry *destIE; // will be filled in by encapsulate()
	IPDatagram *datagram = encapsulate(msg, destIE);

	// route packet
	if (!datagram->getDestAddress().isMulticast())
		hashRoutePacket(datagram, true);
	else
		routeMulticastPacket(datagram, destIE, NULL);
}

void IP::routePacket(IPDatagram *datagram, InterfaceEntry *destIE, bool fromHL)
{
	// TBD add option handling code here

	IPAddress destAddr = datagram->getDestAddress();

	EV << "Routing datagram `" << datagram->getName() << "' with dest=" << destAddr << ": ";

	// check for local delivery
	if (rt->isLocalAddress(destAddr))
	{
		EV << "local delivery\n";
		if (datagram->getSrcAddress().isUnspecified())
			datagram->setSrcAddress(destAddr); // allows two apps on the same host to communicate
		numLocalDeliver++;
		reassembleAndDeliver(datagram);
		return;
	}

	// if datagram arrived from input gate and IP_FORWARD is off, delete datagram
	if (!fromHL && !rt->isIPForwardingEnabled())
	{
		EV << "forwarding off, dropping packet\n";
		numDropped++;
		delete datagram;
		return;
	}

	IPAddress nextHopAddr;

	// if output port was explicitly requested, use that, otherwise use IP routing
	if (destIE)
	{
		EV << "using manually specified output interface " << destIE->getName() << "\n";
		// and nextHopAddr remains unspecified
	}
	else
	{
		// use IP routing (lookup in routing table)
		const IPRoute *re = rt->findBestMatchingRoute(destAddr);

		// error handling: destination address does not exist in routing table:
		// notify ICMP, throw packet away and continue
		if (re==NULL)
		{
			EV << "unroutable, sending ICMP_DESTINATION_UNREACHABLE\n";
			numUnroutable++;
			icmpAccess.get()->sendErrorMessage(datagram, ICMP_DESTINATION_UNREACHABLE, 0);
			return;
		}

		// extract interface and next-hop address from routing table entry
		destIE = re->getInterface();
		nextHopAddr = re->getGateway();
	}

	// set datagram source address if not yet set
	if (datagram->getSrcAddress().isUnspecified())
		datagram->setSrcAddress(destIE->ipv4Data()->getIPAddress());

	// default: send datagram to fragmentation
	EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr << "\n";
	numForwarded++;

	//
	// fragment and send the packet
	//
	fragmentAndSend(datagram, destIE, nextHopAddr);
}

const IPRoute* IP::findHashRoute(const IPDatagram *data, const std::set<IPAddress> *prevHops) {
	SHA1 sha;
	unsigned digest[5];

	sha.Reset();
	int destVal = data->getDestAddress().getInt();
	int currentRouter = rt->getRouterId().getInt();
	sha.Input((unsigned char *) &destVal, sizeof(destVal));
	sha.Input((unsigned char*) &currentRouter, sizeof(currentRouter));
	// and other parameters

	// read the result
	sha.Result(digest);

	// convert the hash value into the form of a bit set
	std::bitset<160> hashValue;
	for (int i = 0; i < 5; i++) {
		unsigned val = digest[i];
		for (int j = 0; j < 32; j++) {
			hashValue[i] = ((val & MSB_MASK) > 0); // read the left-most bit
			val = val << 1; // shift to the left one bit
		}
	}

	return rt->findHashRoute(hashValue, prevHops, data->getDestAddress());
}

void IP::handleNACK(const IPDatagram *datagram)
{
	ASSERT(datagram->getDiscoveryNACK());

	FlowKey key = makeKey(datagram);
	delete datagram;


	IPDatagram *discoPacketCached = disPacketCache[key];
	ASSERT(discoPacketCached != NULL);
	IPDatagram *discoPacket = discoPacketCached->dup(); // we have to duplicate the packet

	int itfIdx = getInterfaceIndex(key);
	ASSERT(itfIdx > -1);

	InterfaceEntry *destIE = ift->getInterface(itfIdx);
	ASSERT(destIE != NULL);
	IPAddress nextHopAddr = nextHopCache[destIE];
	EV<< "Resend Discovery Packet" << endl;

	sendDatagramToOutput(discoPacket, destIE, nextHopAddr);
}

void IP::handleCongestionSignal(IPDatagram *datagram) {
	ASSERT(datagram->getConSIG());

	EV<< "Received congestion signal" << endl;

	const IPRoute *re = rt->findBestMatchingRoute(datagram->getLastHop());
	ASSERT (re != NULL); // there must be a route

	delete datagram;

	InterfaceEntry* ie = re->getInterface();
	int idx = ift->getInterfaceIndex(ie);
	ASSERT(idx > -1);

	int eSwitchCnt = rt->getNumEdgeSwitch();

	if (flowTable == NULL)
		allocateFlowTable();
	ASSERT(flowTable != NULL);


	// check if we already block light flow?
	bool check = true;
	for (int j = 0; j < eSwitchCnt; j++)
		for (int k = 0; k < 3; k++)
			if(flowTable[idx][j][k][0][0]) {
				check = false;
				break;
			}

	if (check) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				flowTable[idx][j][k][0][0] = false;

		return;
	}

	// check if we already block medium flow
	check = true;
	for (int j = 0; j < eSwitchCnt; j++)
		for (int k = 0; k < 3; k++)
			if (flowTable[idx][j][k][0][1]) {
				check = false;
				break;
			}

	if (check) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				flowTable[idx][j][k][0][1] = false;

		return;
	}

	// last resort: block heavy flow
	check = true;
	for (int j = 0; j < eSwitchCnt; j++)
		for (int k = 0; k < 3; k++)
			if (flowTable[idx][j][k][0][2]) {
				check = false;
				break;
			}

	if (check) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				flowTable[idx][j][k][0][1] = false;

		return;
	}
}

void IP::hashRoutePacket(IPDatagram *datagram, bool fromHL)
{
	// TBD add option handling code here
	IPAddress destAddr = datagram->getDestAddress();
	InterfaceEntry *destIE;

	// check for NACK packet
	if (datagram->getDiscoveryNACK()) {
		EV << "NACK packet from " << datagram->getLastHop().str() << endl;
		handleNACK(datagram);
		return;
	}

	EV << "Node " << rt->getRouterId();
	EV << "(Hash) Routing datagram `" << datagram->getName() << "' with dest=" << destAddr << ": ";

	// check for local delivery
	if (rt->isLocalAddress(destAddr))
	{
		EV << "local delivery\n";
		if (datagram->getSrcAddress().isUnspecified())
			datagram->setSrcAddress(destAddr); // allows two apps on the same host to communicate
		numLocalDeliver++;
		EV << "Host: " << rt->getRouterId().str() << " received packet " << datagram->getName() << \
				" from : " << datagram->getSrcAddress().str() << endl;
		reassembleAndDeliver(datagram);
		return;
	}

	// if datagram arrived from input gate and IP_FORWARD is off, delete datagram
	if (!fromHL && !rt->isIPForwardingEnabled())
	{
		EV << "forwarding off, dropping packet\n";
		numDropped++;
		delete datagram;
		return;
	}

	// Check the load of the router and sends out the
	// signal if necessary
	sendLoadSignal(datagram);

	// check if this is a Congestion signal packet
	if (datagram->getConSIG()) {
		handleCongestionSignal(datagram);
		return;
	}

	FlowKey flowKey = makeKey(datagram);
	IPAddress nextHopAddr;
	// if the current node is an end host, we should send to the responsible edge router
	if (!rt->isRouter()) {
		// find the edge router
		nextHopAddr = rt->getEdgeSwitch(rt->getRouterId());
		ASSERT (nextHopAddr != IPAddress::UNSPECIFIED_ADDRESS);
		ASSERT (rt->isNeighbor(nextHopAddr)); // should be a neighbor
		EV << " to edge router : ";

		const IPRoute *re = rt->findBestMatchingRoute(nextHopAddr);
		ASSERT (re != NULL); // there must be a route

		destIE = re->getInterface();
		nextHopAddr = re->getGateway();

		sendDatagramToOutput(datagram, destIE, nextHopAddr);
		numForwarded++;
		EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr;

		return;
	}

	if (rt->isNeighbor(datagram->getDestAddress())) {
		if (datagram->getDiscoveryPacket()) {
			delete datagram;
			EV << "Discovery packet arrives: do not deliver to end host" << endl;
			return;
		}
		EV << " sending to an end host " << endl;
		const IPRoute *re = rt->findBestMatchingRoute(datagram->getDestAddress());
		ASSERT (re != NULL); // there must be a route

		destIE = re->getInterface();
		nextHopAddr = re->getGateway();

		sendDatagramToOutput(datagram, destIE, nextHopAddr);
		numForwarded++;
		EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr;

		return;
	}

	// route from a router
	EV << " with hash routing \n";
	int itfIdx = getInterfaceIndex(flowKey);

	// Existing flow
	if (itfIdx >= 0)
		hrHandleExistingFlow(datagram, itfIdx);
	else { // new flow
		// if the packet's last hop is an end host: we have to generate
		// a discovery packet
		if (rt->isEndHost(datagram->getLastHop()))
			hrEdgeNewFlow(datagram);
		// this first packet out to be the discovery packet
		else if (datagram->getDiscoveryPacket())
			hrHandleDisPacket(datagram);
		// or if the first packet is not the discovery packet?
		// store the packet into a queue
		else
			hrHandleNoDiscovery(datagram);
	}
}

void IP::hrHandleExistingFlow(IPDatagram *datagram, const int idx)
{
	// Drop if a discovery packet arrives again
	if (datagram->getDiscoveryPacket())
	{
		FlowKey flowKey = makeKey(datagram);
		delete disPacketCache[flowKey];
		disPacketCache[flowKey] = datagram;
		EV << "Duplicate discovery packet." << endl;
		return;
	}
	ASSERT(idx >= 0);

	InterfaceEntry *destIE = ift->getInterface(idx);
	ASSERT(destIE != NULL);
	IPAddress nextHopAddr = nextHopCache[destIE];
	EV<< "Found in the entry table" << endl;

	updateFlowTableEntry(destIE);

	// Check if the interface is blocked or not?
	if (isBlocked(destIE, datagram)) {
		hrReroute(datagram);
		return;
	}

	sendDatagramToOutput(datagram, destIE, nextHopAddr);

	// default: send datagram to fragmentation
	EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr;
	numForwarded++;

}

void IP::hrEdgeNewFlow(IPDatagram *datagram)
{
	ASSERT (rt->isEdge());
	EV<< "Creating a discovery packet and route" << endl;

	IPAddress nextHopAddr;
	InterfaceEntry* destIE;

	int attemptCnt = 0;
	do {
		const IPRoute *route = findHashRoute(datagram);
		if (route == NULL || attemptCnt > ift->getNumInterfaces()) { // network is congested, cannot find a route anymore
			EV << "unroutable, dropping the packet\n";
			delete datagram;
			numUnroutable++;
			return;
		}
		nextHopAddr = route->getGateway();
		destIE = route->getInterface();

		updateFlowTableEntry(destIE);

		attemptCnt++;
	}
	while(isBlocked(destIE, datagram));

	// FlowKey
	FlowKey flowKey = makeKey(datagram);

	IPDatagram *disPacket = datagram->dup();
	disPacket->setDiscoveryPacket(true);
	disPacket->setName("dis-packet");

	// Attach the current router id
	IPRecordRouteOption routePath;
	routePath.setRecordAddress(0, rt->getRouterId());
	routePath.setNextAddressPtr(1);

	// Attach the routing information
	disPacket->setRecordRoute(routePath);

	// Store the discovery packet to a cache:
	disPacketCache[flowKey] = disPacket->dup();

	// Add the flow to the entry table
	addFlowEntry(flowKey, destIE);
	nextHopCache[destIE] = nextHopAddr;

	// sends the discovery packet
	sendDatagramToOutput(disPacket, destIE, nextHopAddr);

	// sends the data
	sendDatagramToOutput(datagram, destIE, nextHopAddr);

	// default: send datagram to fragmentation
	EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr;
	numForwarded++;
}

void IP::hrHandleDisPacket(IPDatagram *datagram)
{
	EV<< "This is a discovery packet" << endl;

	// Read the list of previous hops
	std::set<IPAddress> prevHops;
	IPRecordRouteOption& path = datagram->getRecordRoute();
	int pathLen = path.getNextAddressPtr();
	ASSERT(pathLen > 0);
	for (int i = 0; i < pathLen; i++)
		prevHops.insert(path.getRecordAddress(i));

	// Insert the current router into the path
	path.setRecordAddress(pathLen, rt->getRouterId());
	path.setNextAddressPtr(pathLen+1);

	// attach the path to the datagram
	datagram->setRecordRoute(path);

	IPAddress nextHopAddr;
	InterfaceEntry* destIE;

	int attemptCnt = 0;
	do {
		const IPRoute *route = findHashRoute(datagram);
		if (route == NULL || attemptCnt > ift->getNumInterfaces()) { // network is congested, cannot find a route anymore
			EV << "unroutable, dropping the packet\n";
			delete datagram;
			numUnroutable++;
			return;
		}
		nextHopAddr = route->getGateway();
		destIE = route->getInterface();

		updateFlowTableEntry(destIE);
		attemptCnt++;
	}
	while(isBlocked(destIE, datagram));

	// FlowKey
	FlowKey flowKey = makeKey(datagram);

	disPacketCache[flowKey] = datagram->dup();
	// Add the flow to the entry table
	addFlowEntry(flowKey, destIE);
	nextHopCache[destIE] = nextHopAddr;

	// send the data
	sendDatagramToOutput(datagram, destIE, nextHopAddr);

	// default: send datagram to fragmentation
	EV << "output interface is " << destIE->getName() << ", next-hop address: " << nextHopAddr;

	// Empty the queue as well
	FlowQueue *flowQueue = flowQueueCache[flowKey];
	if (flowQueue != NULL) {
		while (!flowQueue->empty()) {
			sendDatagramToOutput(flowQueue->front(), destIE, nextHopAddr);
			flowQueue->pop();
			numForwarded++;
		}
	}
	flowQueueCache.erase(flowKey);
	delete flowQueue;
}

void IP::hrHandleNoDiscovery(IPDatagram *datagram)
{
	EV<< "Discovery packet is lost: queuing" << endl;
	IPAddress prevHop = datagram->getLastHop();

	FlowKey flowKey = makeKey(datagram);
	FlowQueue *flowQueue = flowQueueCache[flowKey];

	// if we're already queuing: only send
	// NAC for every 50 packets
	if (flowQueue != NULL && (flowQueue->size() % 50 != 0)) {
		flowQueue->push(datagram);
		return;
	}
	else if (flowQueue == NULL) {
		flowQueue = new FlowQueue();
		flowQueueCache[flowKey] = flowQueue;
	}

	flowQueue->push(datagram);

	// sends NACK to previous host
	ASSERT (!rt->isEndHost(prevHop));
	EV << "Discovery packet not found" << endl;
	EV << " Prev Hop: " << prevHop.str() << endl;
	// should construct a NACK packet
	IPDatagram *nackPacket = datagram->dup();
	// Note the nackPacket has the same header information with the
	// original packet
	nackPacket->setDiscoveryNACK(true);
	nackPacket->setName("NACK");

	// sends this packet back to the previous hop
	const IPRoute *route = rt->findBestMatchingRoute(prevHop);
	ASSERT(route != NULL);
	EV << " Gateway: " << route->getGateway().str() << endl;

	// set the current hop information
	nackPacket->setLastHop(rt->getRouterId());

	//send the packet
	sendDatagramToOutput(nackPacket, route->getInterface(), route->getGateway());
}

void IP::hrReroute(IPDatagram *datagram) {
	IPAddress nextHopAddr;
	InterfaceEntry* destIE;

	int attemptCnt = 0;
	do {
		const IPRoute *route = findHashRoute(datagram);
		if (route == NULL || attemptCnt > ift->getNumInterfaces()) { // network is congested, cannot find a route anymore
			EV<< "unroutable, dropping the packet\n";
			delete datagram;
			numUnroutable++;
			return;
		}
		nextHopAddr = route->getGateway();
		destIE = route->getInterface();

		updateFlowTableEntry(destIE);
		attemptCnt++;
	}
	while(isBlocked(destIE, datagram));

	// FlowKey
	FlowKey flowKey = makeKey(datagram);

	// Add the flow to the entry table
	int i = ift->getInterfaceIndex(destIE);
	ASSERT (i > -1);
	flowMap[flowKey] = i;

	nextHopCache[destIE] = nextHopAddr;

	// Resends the discovery packet
	IPDatagram *disPacketOld = disPacketCache[flowKey];
	ASSERT(disPacketOld != NULL);
	IPDatagram *disPacket = disPacketOld->dup();

	// Sends the discovery packet first
	sendDatagramToOutput(disPacket, destIE, nextHopAddr);

	// send the data
	sendDatagramToOutput(datagram, destIE, nextHopAddr);
}

void IP::routeMulticastPacket(IPDatagram *datagram, InterfaceEntry *destIE, InterfaceEntry *fromIE)
{
	IPAddress destAddr = datagram->getDestAddress();
	EV << "Routing multicast datagram `" << datagram->getName() << "' with dest=" << destAddr << "\n";

	numMulticast++;

	// DVMRP: process datagram only if sent locally or arrived on the shortest
	// route (provided routing table already contains srcAddr); otherwise
	// discard and continue.
	InterfaceEntry *shortestPathIE = rt->getInterfaceForDestAddr(datagram->getSrcAddress());
	if (fromIE!=NULL && shortestPathIE!=NULL && fromIE!=shortestPathIE)
	{
		// FIXME count dropped
		EV << "Packet dropped.\n";
		delete datagram;
		return;
	}

	// if received from the network...
	if (fromIE!=NULL)
	{
		// check for local delivery
		if (rt->isLocalMulticastAddress(destAddr))
		{
			IPDatagram *datagramCopy = (IPDatagram *) datagram->dup();

			// FIXME code from the MPLS model: set packet dest address to routerId (???)
			datagramCopy->setDestAddress(rt->getRouterId());

			reassembleAndDeliver(datagramCopy);
		}

		// don't forward if IP forwarding is off
		if (!rt->isIPForwardingEnabled())
		{
			delete datagram;
			return;
		}

		// don't forward if dest address is link-scope
		if (destAddr.isLinkLocalMulticast())
		{
			delete datagram;
			return;
		}

	}

	// routed explicitly via IP_MULTICAST_IF
	if (destIE!=NULL)
	{
		ASSERT(datagram->getDestAddress().isMulticast());

		EV << "multicast packet explicitly routed via output interface " << destIE->getName() << endl;

		// set datagram source address if not yet set
		if (datagram->getSrcAddress().isUnspecified())
			datagram->setSrcAddress(destIE->ipv4Data()->getIPAddress());

		// send
		fragmentAndSend(datagram, destIE, datagram->getDestAddress());

		return;
	}

	// now: routing
	MulticastRoutes routes = rt->getMulticastRoutesFor(destAddr);
	if (routes.size()==0)
	{
		// no destination: delete datagram
		delete datagram;
	}
	else
	{
		// copy original datagram for multiple destinations
		for (unsigned int i=0; i<routes.size(); i++)
		{
			InterfaceEntry *destIE = routes[i].interf;

			// don't forward to input port
			if (destIE && destIE!=fromIE)
			{
				IPDatagram *datagramCopy = (IPDatagram *) datagram->dup();

				// set datagram source address if not yet set
				if (datagramCopy->getSrcAddress().isUnspecified())
					datagramCopy->setSrcAddress(destIE->ipv4Data()->getIPAddress());

				// send
				IPAddress nextHopAddr = routes[i].gateway;
				fragmentAndSend(datagramCopy, destIE, nextHopAddr);
			}
		}

		// only copies sent, delete original datagram
		delete datagram;
	}
}

void IP::reassembleAndDeliver(IPDatagram *datagram)
{
	// reassemble the packet (if fragmented)
	if (datagram->getFragmentOffset()!=0 || datagram->getMoreFragments())
	{
		EV << "Datagram fragment: offset=" << datagram->getFragmentOffset()
        		   << ", MORE=" << (datagram->getMoreFragments() ? "true" : "false") << ".\n";

		// erase timed out fragments in fragmentation buffer; check every 10 seconds max
		if (simTime() >= lastCheckTime + 10)
		{
			lastCheckTime = simTime();
			fragbuf.purgeStaleFragments(simTime()-fragmentTimeoutTime);
		}

		datagram = fragbuf.addFragment(datagram, simTime());
		if (!datagram)
		{
			EV << "No complete datagram yet.\n";
			return;
		}
		EV << "This fragment completes the datagram.\n";
	}

	// decapsulate and send on appropriate output gate
	int protocol = datagram->getTransportProtocol();
	cPacket *packet = decapsulateIP(datagram);

	if (protocol==IP_PROT_ICMP)
	{
		// incoming ICMP packets are handled specially
		handleReceivedICMP(check_and_cast<ICMPMessage *>(packet));
	}
	else if (protocol==IP_PROT_IP)
	{
		// tunnelled IP packets are handled separately
		send(packet, "preRoutingOut");
	}
	else
	{
		int gateindex = mapping.getOutputGateForProtocol(protocol);
		send(packet, "transportOut", gateindex);
	}
}

cPacket *IP::decapsulateIP(IPDatagram *datagram)
{
	// decapsulate transport packet
	InterfaceEntry *fromIE = getSourceInterfaceFrom(datagram);
	cPacket *packet = datagram->decapsulate();

	// create and fill in control info
	IPControlInfo *controlInfo = new IPControlInfo();
	controlInfo->setProtocol(datagram->getTransportProtocol());
	controlInfo->setSrcAddr(datagram->getSrcAddress());
	controlInfo->setDestAddr(datagram->getDestAddress());
	controlInfo->setDiffServCodePoint(datagram->getDiffServCodePoint());
	controlInfo->setInterfaceId(fromIE ? fromIE->getInterfaceId() : -1);

	// original IP datagram might be needed in upper layers to send back ICMP error message
	controlInfo->setOrigDatagram(datagram);

	// attach control info
	packet->setControlInfo(controlInfo);

	return packet;
}


void IP::fragmentAndSend(IPDatagram *datagram, InterfaceEntry *ie, IPAddress nextHopAddr)
{
	int mtu = ie->getMTU();

	// check if datagram does not require fragmentation
	if (datagram->getByteLength() <= mtu)
	{
		sendDatagramToOutput(datagram, ie, nextHopAddr);
		return;
	}

	int headerLength = datagram->getHeaderLength();
	int payload = datagram->getByteLength() - headerLength;

	int noOfFragments =
			int(ceil((float(payload)/mtu) /
					(1-float(headerLength)/mtu) ) ); // FIXME ???

	// if "don't fragment" bit is set, throw datagram away and send ICMP error message
	if (datagram->getDontFragment() && noOfFragments>1)
	{
		EV << "datagram larger than MTU and don't fragment bit set, sending ICMP_DESTINATION_UNREACHABLE\n";
		icmpAccess.get()->sendErrorMessage(datagram, ICMP_DESTINATION_UNREACHABLE,
				ICMP_FRAGMENTATION_ERROR_CODE);
		return;
	}

	// create and send fragments
	EV << "Breaking datagram into " << noOfFragments << " fragments\n";
	std::string fragMsgName = datagram->getName();
	fragMsgName += "-frag";

	// FIXME revise this!
	for (int i=0; i<noOfFragments; i++)
	{
		// FIXME is it ok that full encapsulated packet travels in every datagram fragment?
		// should better travel in the last fragment only. Cf. with reassembly code!
		IPDatagram *fragment = (IPDatagram *) datagram->dup();
		fragment->setName(fragMsgName.c_str());

		// total_length equal to mtu, except for last fragment;
		// "more fragments" bit is unchanged in the last fragment, otherwise true
		if (i != noOfFragments-1)
		{
			fragment->setMoreFragments(true);
			fragment->setByteLength(mtu);
		}
		else
		{
			// size of last fragment
			int bytes = datagram->getByteLength() - (noOfFragments-1) * (mtu - datagram->getHeaderLength());
			fragment->setByteLength(bytes);
		}
		fragment->setFragmentOffset( i*(mtu - datagram->getHeaderLength()) );

		sendDatagramToOutput(fragment, ie, nextHopAddr);
	}

	delete datagram;
}


IPDatagram *IP::encapsulate(cPacket *transportPacket, InterfaceEntry *&destIE)
{
	IPControlInfo *controlInfo = check_and_cast<IPControlInfo*>(transportPacket->removeControlInfo());
	IPDatagram *datagram = encapsulate(transportPacket, destIE, controlInfo);
	delete controlInfo;
	return datagram;
}

IPDatagram *IP::encapsulate(cPacket *transportPacket, InterfaceEntry *&destIE, IPControlInfo *controlInfo)
{
	IPDatagram *datagram = createIPDatagram(transportPacket->getName());
	datagram->setByteLength(IP_HEADER_BYTES);
	datagram->encapsulate(transportPacket);

	// set source and destination address
	IPAddress dest = controlInfo->getDestAddr();
	datagram->setDestAddress(dest);

	// IP_MULTICAST_IF option, but allow interface selection for unicast packets as well
	destIE = ift->getInterfaceById(controlInfo->getInterfaceId());

	IPAddress src = controlInfo->getSrcAddr();

	// when source address was given, use it; otherwise it'll get the address
	// of the outgoing interface after routing
	if (!src.isUnspecified())
	{
		// if interface parameter does not match existing interface, do not send datagram
		if (rt->getInterfaceByAddress(src)==NULL)
			opp_error("Wrong source address %s in (%s)%s: no interface with such address",
					src.str().c_str(), transportPacket->getClassName(), transportPacket->getFullName());
		datagram->setSrcAddress(src);
	}

	// set other fields
	datagram->setDiffServCodePoint(controlInfo->getDiffServCodePoint());

	datagram->setIdentification(curFragmentId++);
	datagram->setMoreFragments(false);
	datagram->setDontFragment (controlInfo->getDontFragment());
	datagram->setFragmentOffset(0);

	short ttl;
	if (controlInfo->getTimeToLive() > 0)
		ttl = controlInfo->getTimeToLive();
	else if (datagram->getDestAddress().isLinkLocalMulticast())
		ttl = 1;
	else if (datagram->getDestAddress().isMulticast())
		ttl = defaultMCTimeToLive;
	else
		ttl = defaultTimeToLive;

	datagram->setTimeToLive(ttl);
	datagram->setTransportProtocol(controlInfo->getProtocol());

	// setting IP options is currently not supported

	return datagram;
}

IPDatagram *IP::createIPDatagram(const char *name)
{
	return new IPDatagram(name);
}

void IP::sendDatagramToOutput(IPDatagram *datagram, InterfaceEntry *ie,
		IPAddress nextHopAddr) {
	// set datagram source address if not yet set
	if (datagram->getSrcAddress().isUnspecified())
		datagram->setSrcAddress(rt->getRouterId());

	// set the current node's IP as lastHop
	datagram->setLastHop(rt->getRouterId());

	// send out datagram to ARP, with control info attached
	IPRoutingDecision *routingDecision = new IPRoutingDecision();
	routingDecision->setInterfaceId(ie->getInterfaceId());
	routingDecision->setNextHopAddr(nextHopAddr);
	datagram->setControlInfo(routingDecision);

	EV << " current IE throughput: " << ie->getThroughput() << endl;

	send(datagram, queueOutGate);
}

IP::FlowKey IP::makeKey(const IPDatagram *datagram) {
	FlowKey key (datagram->getSrcAddress(), datagram->getDestAddress(), \
			0, 0, 0);
	return key;
}

void IP::addFlowEntry(const FlowKey& key, const InterfaceEntry *ie) {
	ASSERT(flowMap.find(key) == flowMap.end());

	int i = ift->getInterfaceIndex(ie);

	ASSERT (i > -1);

	flowMap[key] = i;
}

int IP::getInterfaceIndex(const FlowKey &key) {
	FlowMap::iterator it = flowMap.find(key);
	if (it == flowMap.end())
		return -1;

	return it->second;
}

void IP::allocateFlowTable()
{
	if (flowTable != NULL)
		return;

	// Allocate the flow table
	int numIntf = ift->getNumInterfaces();
	int eSwitchCnt = rt->getNumEdgeSwitch();

	flowTable = new bool****[numIntf];
	for (int i = 0; i < numIntf; i++) {
		int eSwitchCnt = rt->getNumEdgeSwitch();
		flowTable[i] = new bool***[eSwitchCnt];
		for (int j = 0; j < eSwitchCnt; j++) {
			// 3 types of traffic
			flowTable[i][j] = new bool**[3];
			for (int k = 0; k < 3; k++) {
				// 1 type of priority (should be more, but we're not using
				// any other prioriy
				flowTable[i][j][k] = new bool*[1];

				// three types of load level
				flowTable[i][j][k][0] = new bool[3];

				// enable the flow to pass through all interfaces
				for (int l = 0; l < 3; l++)
					flowTable[i][j][k][0][l] = true;
			}
		}
	}
}

/**
 * Updates the blocking bits according to the current load of
 * the specified interface entry
 */
void IP::updateFlowTableEntry(InterfaceEntry *ie)
{
	if (flowTable == NULL)
		allocateFlowTable();

	int idx = ift->getInterfaceIndex(ie);
	ASSERT(idx >= 0);
	int eSwitchCnt = rt->getNumEdgeSwitch();

	double throughput = ie->getThroughput();
	// threshold 1: block all lightly loaded flow
	if (throughput > threshold_light) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				flowTable[idx][j][k][0][0] = false;
	}

	// threshold 2: block all medium loaded flow
	if (throughput > threshold_medium) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				flowTable[idx][j][k][0][1] = false;
	}

	// reset if the rate drops
	if (throughput <= threshold_reset) {
		for (int j = 0; j < eSwitchCnt; j++)
			for (int k = 0; k < 3; k++)
				for (int p = 0; p < 3; p++)
					flowTable[idx][j][k][0][p] = true;
	}
}

/**
 * Returns if a flow is blocked on this interface or not
 */
bool IP::isBlocked(const InterfaceEntry *ie, const IPDatagram *datagram)
{
	int idx = ift->getInterfaceIndex(ie);
	ASSERT(idx >= 0);
	IPAddress eSwitch = rt->getEdgeSwitch(datagram->getDestAddress());
	int eSwitchIdx = rt->getEdgeSwitchIdx(eSwitch);

	//#TODO: load level
	return (!flowTable[idx][eSwitchIdx][0][0][0]);
}

void IP::sendLoadSignal(const IPDatagram *datagram) {
	IPAddress lastHop = datagram->getLastHop();
	if (rt->isEndHost(lastHop) || lastHop == IPAddress::UNSPECIFIED_ADDRESS) // skip end host
		return;

	int n = ift->getNumInterfaces();
	bool isHeavyloaded = true;
	bool toClear = true;
	for (int i = 0; i < n; i++) {
		InterfaceEntry *ie = ift->getInterface(i);
		ASSERT(ie != NULL);
		if (ie->isLoopback() || ie->isDown())
			continue;

		double thruput = ie->getThroughput();
		if (thruput < threshold_congestion)
			isHeavyloaded = false;

		if (thruput < 0.5)
			toClear = false;
	}

	// if not heavy loaded, we should clear the map
	if(toClear) {
		conSigMap.clear();
		return;
	}

	if (!isHeavyloaded)
		return;

	// check if we already sent a feedback signal to this destination
	std::map<IPAddress, int>::iterator it = conSigMap.find(lastHop);

	// sends out every 50 packets received from the neighbor
	if (it == conSigMap.end() || it->second == 50) {
		IPDatagram* conSignal = datagram->dup();
		conSignal->setName("Con-signal");
		conSignal->setLastHop(rt->getRouterId());
		conSignal->setConSIG(true);

		const IPRoute *route = findHashRoute(datagram);
		ASSERT(route != NULL);

		IPAddress nextHopAddr = route->getGateway();
		InterfaceEntry *destIE = route->getInterface();

		EV << "Sends congestion signal\n";

		//send the packet
		sendDatagramToOutput(conSignal, route->getInterface(), route->getGateway());

		// Reset the counter
		conSigMap[lastHop] = 0;
	}
	else
		conSigMap[lastHop] = it->second + 1;

}
